package com.jiang.daily.Q3318;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author Jiang
 * @version 1.0
 * @date 2025/11/04 10:51
 */
class Solution {
    public int[] findXSum(int[] nums, int k, int x) {
        // 使用 HashMap 来存储每个数字及其出现的频率
        Map<Integer, Integer> map = new HashMap<>();

        // 初始化滑动窗口，先放入前 k-1 个元素
        for (int i = 0; i < k - 1; i++) {
            map.compute(nums[i], (key, v) -> v == null ? 1 : v + 1);
        }

        int n = nums.length;
        int[] res = new int[n - k + 1];

        // 滑动窗口主循环
        // l 是窗口左边界, r 是窗口右边界
        for (int l = 0, r = k - 1; r < n; l++, r++) {
            // 1. 将新的右边界元素加入窗口，并更新频率
            map.compute(nums[r], (key, v) -> v == null ? 1 : v + 1);

            // 2. 将 map 的 entry set 转换为 list 以便排序
            List<Map.Entry<Integer, Integer>> list = new ArrayList<>(map.entrySet());

            // 3. 对 list 进行自定义排序，首先按频率降序, 频率相同则按数字本身降序
            list.sort((a, b) -> {
                int cnt = b.getValue().compareTo(a.getValue());
                if (cnt != 0) {
                    return cnt;
                } else {
                    return b.getKey().compareTo(a.getKey());
                }
            });

            // 4. 遍历排序后的前 x 个元素 (如果元素总数不足 x，则遍历全部)
            for (int i = 0; i < x && i < list.size(); i++) {
                res[l] += list.get(i).getKey() * list.get(i).getValue();
            }

            // 5. 移除窗口的左边界元素，并更新频率
            map.compute(nums[l], (key, v) -> --v);
            if (map.get(nums[l]) == 0) {
                map.remove(nums[l]);
            }
        }
        return res;
    }
}
